package Q2;

import java.util.*;

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here

        //小根堆
        List<ListNode> temp = new ArrayList<>();

        for (ListNode list : lists) {
            ListNode cur = list;
            while (cur != null) {
                temp.add(new ListNode(cur.val));
                cur = cur.next;
            }
        }

        Collections.sort(temp, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        ListNode ret = new ListNode(-1);

        ListNode cur = ret;
        for (ListNode node : temp) {
            cur.next = node;
            cur = node;
        }

        return ret.next;
    }
}